翻訳と辞書 Words near each other ・ Grembach Łódź ・ Grembergen ・ Grembergen (disambiguation) ・ Gregynog Press ・ Gregynog Young Musicians Competition ・ Gregório Amúrrio ・ Gregório Bondar ・ Gregório de Matos ・ Gregório Duvivier ・ Gregório Freixo ・ Gregório Lopes ・ Gregório Nunes Coronel ・ Gregório River ・ Gregório River (Amazonas) ・ Gregório River (Goiás) ・ Greibach normal form ・ Greibach's theorem ・ Greiche and Scaff ・ Greider ・ Greidys Gil ・ Greif ・ Greif (brigantine) ・ Greif, Inc. ・ Greifenbach ・ Greifenberg ・ Greifenberg Castle ・ Greifenburg ・ Greifenhagen ・ Greifensee ・ Greifensee Castle Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Greibach normal form ： ウィキペディア英語版 Greibach normal form In formal language theory, a context-free grammar is in Greibach normal form (GNF) if the right-hand sides of all production rules start with a terminal symbol, optionally followed by some variables. A non-strict form allows one exception to this format restriction for allowing the empty word (epsilon, ε) to be a member of the described language. The normal form was established by Sheila Greibach and it bears her name. More precisely, a context-free grammar is in Greibach normal form, if all production rules are of the form: :$A\; \backslash to\; a\; A\_1\; A\_2\; \backslash cdots\; A\_n$ or :$S\; \backslash to\; \backslash varepsilon$ where $A$ is a nonterminal symbol, $a$ is a terminal symbol, $A\_1\; A\_2\; \backslash ldots\; A\_n$ is a (possibly empty) sequence of nonterminal symbols not including the start symbol, $S$ is the start symbol, and ''ε'' is the empty word. Observe that the grammar does not have left recursions. Every context-free grammar can be transformed into an equivalent grammar in Greibach normal form. Various constructions exist. Some do not permit the second form of rule and cannot transform context-free grammars that can generate the empty word. For one such construction the size of the constructed grammar is ''O(n4)'' in the general case and ''O(n3)'' if no derivation of the original grammar consists of a single nonterminal symbol, where ''n'' is the size of the original grammar. This conversion can be used to prove that every context-free language can be accepted by a real-time pushdown automaton, i.e., the automaton reads a letter from its input every step. Given a grammar in GNF and a derivable string in the grammar with length ''n'', any top-down parser will halt at depth ''n''. == See also == * Backus–Naur form * Chomsky normal form * Kuroda normal form 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Greibach normal form」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.